package week_03;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Preorder_589 {


    public List<Integer> ans = new ArrayList<>();

    public List<Integer> preorder1(Node root) {
        traversal(root);
        return ans;
    }

    public void traversal(Node node) {
        if (node == null) return;
        // 加入结果
        ans.add(node.val);
        //while 处理每颗子树
        for (Node child : node.children) {
            traversal(child);
        }
    }

    public List<Integer> preorder(Node root) {
        // while 迭代实现前序遍历
        List<Integer> ans = new ArrayList<>();
        // 栈来保证遍历的前序顺序
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            Node cur=stack.pop();
            if(cur==null) break;
            ans.add(cur.val);
            for(int i=cur.children.size()-1;i>=0;i--){
                stack.push(cur.children.get(i));
            }
        }
        return ans;
    }
}
